题目分析

本题是第312场周赛的最后一题，题目的难度比较大，不要求小伙伴能够在第一次遇到时就能成功求解出来，但是要理解本题的思想。

并查集

因为好路径的条件是开始节点和结束节点相同，并且中间节点值都小于开始节点值。

一开始每个节点都是独立的，我们可以从小到大遍历节点，并逐渐连通这个图，遍历到某个点X时，将小于X的点都和X进行连接。全部连接完毕后，查看值为X的点都在哪些连通块内，那么这些连通块中的点一定是满足条件的。

比如某个连通块内又5个值为X的点，那么对于这个连通块来说，一共有 $C_5^2$ 个路径，因为每个单独的点也是一个路径，因此结果为 $C_5^2 + 5$，对于$ C_k^2 + k $其实是等于 $ C_{k + 1}^2$的，因此是k x (k + 1) / 2。

算法思路就出来了，可以同并查集合并点，然后根据root是否相同，判断是否在同一块区域。然后用并查集，key为root，value的数量，可以查到相同区域值为X的元素数量，res += val x (val + 1) / 2即可。

因为最多n个点，所以并查集合并的时间复杂度是O(n)的，因此限制算法时间的操作是排序。算法的**时间复杂度为O(nlog(n))，空间复杂度为O(n)**。

class Solution {
    private int[] root;

    private int getRoot(int x) {
        if (root[x] != x) {
            root[x] = getRoot(root[x]);
        }
        return root[x];
    }

    public int numberOfGoodPaths(int[] vals, int[][] edges) {
        int n = vals.length;
        List<Integer>[] g = new List[n];
        Arrays.setAll(g, o -> new ArrayList<>());
        for (int[] ed : edges) {
            g[ed[0]].add(ed[1]);
            g[ed[1]].add(ed[0]);
        }
        root = new int[n];
        for (int i = 0; i < n; i++) {
            root[i] = i;
        }
        Integer[] arr = IntStream.range(0, n).boxed().toArray(Integer[]::new);
        Arrays.sort(arr, Comparator.comparingInt(o -> vals[o]));
        int res = 0;
        for (int left = 0; left < n; left++) {
            int right = left + 1;
            while (right < n && vals[arr[right]] == vals[arr[left]]) {
                right++;
            }
            for (int k = left; k < right; k++) {
                int rootK = getRoot(arr[k]);
                for (int x : g[arr[k]]) {
                    if (vals[x] <= vals[arr[left]]) {
                        int rootX = getRoot(x);
                        if (rootX != rootK) {
                            root[rootX] = rootK;

                        }
                    }
                }
            }
            HashMap<Integer, Integer> map = new HashMap<>();
            for (int k = left; k < right; k++) {
                int rootK = root[getRoot(arr[k])];
                map.put(rootK, map.getOrDefault(rootK, 0) + 1);
            }
            for (int x : map.values()) {
                res += x * (x + 1) / 2;
            }
            left = right - 1;
        }
        return res;
    }
}

刷题总结

遇到这种和图、大小有关的题目，要能够想到排序+并查集，这是本题想要教会小伙伴的思路。